/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        99.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 11:39
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
 */
#include "tree_node.h"
#include <stack>

using namespace std;

class Solution {
public:
    void recoverTree(TreeNode *root) {
        TreeNode *x = nullptr;
        TreeNode *y = nullptr;
        TreeNode *pre = nullptr;
        stack<TreeNode *> stack;
        while (root != nullptr || !stack.empty()) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (pre != nullptr && root->val < pre->val) {
                y = root;
                if (x == nullptr)
                    x = pre;
                else
                    break;
            }
            pre = root;
            root = root->right;
        }
        swap(x->val,y->val);
    }
};